//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出："a"
// 
//
// 示例 4： 
//
// 
//输入：s = "ac"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母（大写和/或小写）组成 
// 
// Related Topics 字符串 动态规划 
// 👍 3576 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {

        char[] sChar = s.toCharArray();
        int length = s.length();

        int maxLength = 1;
        int begin = 0;

        boolean[][] dictionary = new boolean[length][length];

        for (int i = 0; i < length; i++) {
            dictionary[i][i] = true;
        }

        for (int j = 1; j < length; j++) {
            for (int i = 0; i < j ; i++) {
                if(sChar[i] != sChar[j]){
                    dictionary[i][j] = false;
                }else {
                    if( j - i < 3){
                        dictionary[i][j] = true;
                    }else {
                        dictionary[i][j] = dictionary[i + 1][j - 1];
                    }
                }

                if (dictionary[i][j] && j - i + 1 > maxLength){
                    maxLength = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin + maxLength);

    }
}
//leetcode submit region end(Prohibit modification and deletion)
